#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 2e5+10;
const int inf = 0x3f3f3f3f;

int n,m,a,k,A[N];
ll modi[N],b[N];

struct seg{
	int l,r;
}p[N];

bool operator < (seg x,seg y){return x.l ^ y.l ? x.l < y.l : x.r < y.r;}

bool check(ll x){
	priority_queue<int> s; while(s.size()) s.pop(); int cur = 1; int nowused = 0; memset(modi,0,sizeof(modi));
	for(int i = 1;i <= n;i++) b[i] = (x - A[i] + a - 1) / a;
	for(int i = 1;i <= n;i++){
		while(cur <= m && p[cur].l == i) s.push(p[cur].r),cur++;
		modi[i] += modi[i-1];
		ll need = b[i] - modi[i];
		while(need > 0){
			if(s.empty()) return 0;
			int tt = s.top();
			if(tt < i) return 0;
			nowused ++; modi[i]++; modi[tt+1]--;
			need--; if(nowused > k) return 0;
			s.pop();
		}
	}return 1;
}

void solve(){
	n = in,m = in,k = in,a = in; int mn = inf;
	for(int i = 1;i <= n;i++) A[i] = in,mn = min(mn,A[i]);
	for(int i = 1;i <= m;i++) p[i].l = in,p[i].r = in;
	sort(p+1,p+m+1);
	ll l = mn,r = mn + 1ll * a * k,ans = l;
	while(l <= r){
		ll mid = l+r>>1;
		if(check(mid)) ans = max(ans,mid),l = mid + 1;
		else r = mid - 1;
	}
	printf("%lld\n",ans);
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	int test = in;
	while(test--) solve();
	return 0;
}

